#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
#include "conio.h"

using namespace std;

int longest_polindromic_subsequence_non_rec(const vector<int> &seq)
{
	vector<vector<int>> table(seq.size());
	for (int i = 0; i < seq.size(); ++i)
		table[i].resize(seq.size());

	for (int i = 0; i < seq.size(); ++i)
	{
		for (int j = i; j >= 0; --j)
		{
			if (seq[i] == seq[j])
			{
				if (i == 0 || j == seq.size()-1 || i == j)					
					table[i][j] = 1;
				else
					table[i][j] = table[i-1][j+1] + 2;
			}
			else
			{
				if (i == 0 || j == seq.size()-1)
					table[i][j] = 1;
				else
					table[i][j] = max(table[i-1][j], table[i][j+1]);
			}
		}
	}

	return *max_element(table[seq.size()-1].begin(), table[seq.size()-1].end());
}

int longest_polindromic_subsequence(const vector<int> &seq, int l, int r)
{
	if (l > r)
		return 0;

	if (seq[l] == seq[r])
	{
		return longest_polindromic_subsequence(seq, l+1, r-1) + 2 - (l==r?1:0);
	}
	else
	{
		return max(longest_polindromic_subsequence(seq, l+1, r),
			longest_polindromic_subsequence(seq, l, r-1));
	}
}

void main()
{
	int seq_len;
	cout << "Input sequence length:" << endl;
	cin >> seq_len;

	vector<int> seq(seq_len);
	cout << "Input sequence:" << endl;
	for (int i = 0; i < seq_len; ++i)
		cin >> seq[i];

	cout << "Length of the longest polindromic substring: " << longest_polindromic_subsequence_non_rec(seq);
	_getch();
}